/**
 * 979. 在二叉树中分配硬币
 * https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/
 */
public class Solutions_979 {
    public static void main(String[] args) {
//        TreeNode root = new TreeNode(3);
//        root.left = new TreeNode(0);
//        root.right = new TreeNode(0);  // output: 2

//        TreeNode root = new TreeNode(0);
//        root.left = new TreeNode(3);
//        root.right = new TreeNode(0);  // output: 3

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(0);
        root.right = new TreeNode(2);  // output: 2

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(0);
//        root.right = new TreeNode(0);
//        root.left.right = new TreeNode(3);  // output: 4

        int result = distributeCoins(root);
        System.out.println(result);
    }

    private static int res = 0;
    public static int distributeCoins(TreeNode root) {
        dfs(root);
        return res;
    }

    public static int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 左子节点能够多余出 leftCoin 个硬币
        int leftCoin = dfs(root.left);
        // 右子节点能够多余出 leftCoin 个硬币
        int rightCoin = dfs(root.right);
        // 多余多少个硬币，即移动多少个硬币到上一节点
        // 缺少多少个硬币，即需要从父节点移动多少个硬币过来
        res += Math.abs(leftCoin) + Math.abs(rightCoin);
        // 节点上仅保留一个硬币，其余的给父节点
        return root.val + leftCoin + rightCoin - 1;
    }
}
